Theo ước tính, loài người bắt đầu định cư tại lục địa Úc từ 42.000 đến 48.000 năm trước,[31] các di dân này có thể đã từ khu vực mà nay là Đông Nam Á và đến theo các cầu lục địa và vượt biển khoảng cách ngắn. Các cư dân đầu tiên này có thể là tổ tiên của thổ dân Úc hiện nay.[32] Khi người châu Âu tiến hành định cư vào cuối thế kỷ XVIII, hầu hết thổ dân Úc là những người săn bắn-hái lượm, có một văn hóa truyền khẩu phức tạp và các giá trị tinh thần dựa trên sùng kính thổ địa và tin tưởng vào thời mộng ảo. Người quần đảo Eo biển Torres thuộc nhóm dân tộc Melanesia, họ ban đầu là những người làm vườn và săn bắn-hái lượm.[33] các ngư dân từ Đông Nam Á hàng hải thỉnh thoảng cũng đi đến các vùng duyên hải và vùng biển bắc bộ của Úc.[34]

Nhà hàng hải người Hà Lan Willem Janszoon là người châu Âu đầu tiên được ghi chép là đã trông thấy đại lục Úc, và là người châu Âu đầu tiên được ghi chép là đã đổ bộ lên lục địa Úc. Ông trông thấy bờ biển của bán đảo Cape York vào đầu năm 1606, và tiến hành đổ bộ vào ngày 26 tháng 2 tại sông Pennefather gần thị trấn Weipa ngày nay tại Cape York.[35] Người Hà Lan vẽ hải đồ toàn bộ đường bờ biển tây bộ và bắc bộ và đặt tên cho lục địa đảo là "Tân Hà Lan" trong thế kỷ XVII, song không tiến hành nỗ lực định cư.[35] Nhà thám hiểm người Anh William Dampier đổ bộ lên bờ biển tây-bắc của Tân Hà Lan vào năm 1688 và tiếp một lần nữa vào năm 1699 trong một chuyến đi trở lại.[36] Năm 1770, James Cook đi thuyền dọc theo và vẽ bản đồ bờ biển phía đông, ông định danh cho nó là New South Wales và tuyên bố chủ quyền cho Anh Quốc.[37] Sau khi mất 13 thuộc địa tại Bắc Mỹ vào năm 1780, Chính phủ Anh cử một hạm đội tàu, "Đệ Nhất hạm đội", dưới quyền chỉ huy của Thuyền trưởng Arthur Phillip, đi thiết lập một thuộc địa lưu đày mới tại New South Wales. Một trại được lập ra và quốc kỳ được kéo lên tại Sydney Cove, Port Jackson, vào ngày 26 tháng 1 năm 1788,[18] ngày này trở thành ngày quốc khánh của Úc.

Một khu định cư của Anh Quốc được thiết lập tại đất Van Diemen, nay là Tasmania, vào năm 1803 và đảo này trở thành một thuộc địa riêng biệt vào năm 1825.[38] Anh Quốc chính thức tuyên bố chủ quyền đối với phần tây bộ của Tây Úc (thuộc địa sông Swan) vào năm 1828.[39] Các thuộc địa riêng biệt được tách ra từ các lãnh thổ của New South Wales: Nam Úc vào năm 1836, Victoria vào năm 1851, và Queensland vào năm 1859.[40] Lãnh thổ phương Bắc được tách ra từ Nam Úc và thành lập vào năm 1911.[41] Nam Úc được thành lập với tình trạng là một "tỉnh tự do" – nơi này chưa từng là một thuộc địa lưu đày.[42] Victoria và Tây Úc cũng được thành lập với tình trạng "tự do", song về sau chấp thuận các tù nhân được vận chuyển đến.[43][44] Những người định cư tại New South Wales tiến hành một chiến dịch mà cuối cùng đã dẫn đến việc chấm dứt vận chuyển tù nhân đến thuộc địa này; tàu chở tù nhân cuối cùng đến vào năm 1848.[45]

Theo ước tính, dân số thổ dân là từ 750.000 đến 1.000.000 vào thời điểm người châu Âu bắt đầu định cư,[46] song dân số của họ suy giảm trong 150 năm sau đó, chủ yếu do bệnh truyền nhiễm.[47] Một chính sách "đồng hóa" của chính phủ bắt đầu với Đạo luật Bảo vệ thổ dân 1869, kết quả là nhiều trẻ em thổ dân bị đưa ra khỏi gia đình và cộng đồng của chúng, hành động này cũng có thể góp phần vào sự suy giảm của dân số người bản địa.[48] Chính phủ Liên bang giành được quyền ra các điều luật tôn trọng thổ dân sau cuộc trưng cầu dân ý năm 1967.[49] Quyền sở hữu đất đai theo truyền thống—quyền sở hữu của thổ dân—không được công nhận cho đến năm 1992, khi Tòa Cao đẳng Úc ra phán quyết Mabo v Queensland (số 2) lật đổ học thuyết pháp lý rằng Úc là "đất vô chủ" trước khi người châu Âu chiếm giữ.[50]

Một cơn sốt vàng bắt đầu tại Úc vào đầu thập kỷ 1850[51] và Nổi loạn Eureka năm 1854 nhằm chống phí cấp phép khai mỏ là một biểu hiện bất tuân dân sự đầu tiên.[52] Từ năm 1855 đến năm 1890, sáu thuộc địa dần giành được quyền có chính phủ chịu trách nhiệm, tự quản lý hầu hết các vấn đề của họ song vẫn là một bộ phận của Đế quốc Anh.[53] Văn phòng Thuộc địa tại Luân Đôn duy trì quyền kiểm soát trên một số vấn đề, đáng chú ý là các quan hệ đối ngoại,[54] phòng thủ,[55] và vận chuyển quốc tế.

Ngày 1 tháng 1 năm 1901, đạt được liên minh của các thuộc địa sau một thập kỷ lên kế hoạch, thảo luận và bỏ phiếu.[56] Thịnh vượng chung Úc được thành lập và trở thành một nước tự trị của Đế quốc Anh vào năm 1907. Lãnh thổ Thủ đô Liên bang (sau đổi tên thành Lãnh thổ Thủ đô Úc) được thành lập vào năm 1911 để làm địa điểm của thủ đô liên bang tương lai- Canberra. Trong khi Canberra được xây dựng, Melbourne là nơi tạm thời đặt trụ sở chính phủ từ năm 1901 đến năm 1927.[57] Quyền kiểm soát Lãnh thổ phương Bắc được chuyển từ chính phủ Nam Úc sang nghị viện liên bang vào năm 1911.[58] Năm 1914, Úc cùng Anh Quốc chiến đấu trong Chiến tranh thế giới thứ nhất, với sự ủng hộ của Đảng Tự do Thịnh vượng chung đang chuyển giao và Đảng Lao động Úc đang tiếp nhận chính phủ.[59][60] Úc tham gia trong nhiều trận chiến lớn tại Mặt trận phía Tây.[61] Trong số khoảng 416.000 người từng phục vụ, khoảng 60.000 chết và 152.000 bị thương.[62] Nhiều người Úc nhìn nhận thất bại của Quân đoàn Úc và New Zealand tại Gallipoli là mốc quốc gia đản sinh, đó là hành động quân sự lớn đầu tiên của Úc.[63][64]Chiến dịch đường Kokoda được nhiều người nhìn nhận là một sự kiện định nghĩa quốc gia tương tự trong Chiến tranh thế giới thứ hai.[65]

Đạo luật Westminster 1931 của Anh Quốc chính thức chấm dứt hầu hết các liên kết hiến pháp giữa Úc và Anh Quốc. Úc chuẩn thuận nó vào năm 1942,[66] song tuyên bố rằng đạo luật có hiệu lực từ năm 1939 để xác nhận tính hợp lệ của các pháp luật do Nghị viện Úc thông qua trong Chiến tranh thế giới thứ hai.[67][68] Bất ngờ trước thất bại của Anh Quốc tại châu Á vào năm 1942 và mối đe dọa Nhật Bản xâm chiếm khiến Úc hướng sang Hoa Kỳ như một đồng minh và nước bảo hộ mới.[69] Từ năm 1951, Úc trở thành một đồng minh quân sự chính thức của Hoa Kỳ, theo hiệp định ANZUS.[70] Sau Chiến tranh thế giới thứ hai, Úc khuyến khích nhập cư từ châu Âu. Kể từ thập niên 1970 và sau khi bãi bỏ chính sách Úc Da trắng, nhập cư từ châu Á và những nơi khác cũng tăng tiến.[71] Kết quả là Úc có sự biến đổi về các mặt nhân khẩu học, văn hóa, tự nhận thức về bản thân.[72] Việc thông qua Đạo luật Úc năm 1986 đã đoạn tuyệt các quan hệ hiến pháp cuối cùng giữa Úc và Anh Quốc, theo đó chấm dứt hoàn toàn vai trò của Anh Quốc trong chính phủ của các bang của Úc, và kết thúc quyền chọn lựa chống án pháp lý lên Xu mật viện tại Luân Đôn.[73] Trong một cuộc trưng cầu dân ý vào năm 1999, 55% số cử tri và đa số tại mọi bang đã bác bỏ một đề xuất trở thành một nước cộng hòa với một tổng chống được bầu từ ít nhất 2/3 số phiếu tại cả hai viện của Nghị viện Úc. Kể từ khi Gough Whitlam trở thành thủ tướng vào năm 1972,[74] chính sách đối ngoại của Úc ngày càng tập trung vào các mối quan hệ với các quốc gia khác trong vành đai Thái Bình Dương, trong khi duy trì quan hệ gần gũi với các đồng minh và đối tác thương mại truyền thống của mình.[75]